algorithm and data structure

PE424001 Algorithm and Data Structure
Assignment 1
(25% of the module score)
Q1. (10 Marks) With an infix expression in the form of :
((A-B)+C*(D+E))-(F+G)
a) What is the prefix expression? Illustrates your steps using a Stack data structure. (4 Marks)
b) Verify your result by assigning the values to variables and shows your steps. (4 Marks)
A=7 , B=6, C=5, D=4, E=3, F=2, G=1
c) What is the final answer in b)? (1 Mark)
d) Give one example in which Stack is always used. (1 Mark)
Q2. (10 Marks) Given an input array
[ 5 2 6 1 7 9 4 3]
a) Trace the action of:
1 Selection Sort (1 Mark)
2 Insertion Sort (1 Mark)
b) Refer to the following number list which is sorted by bubble sort and in ascending order. (5 Marks)
Initial list: 18, 17, 13, 26, 10, 14, 24
After 1st pass: 17 13 18 10 14 24 26
After 2nd pass: 13 17 10 14 18 24 26
After 3rd pass: 13 10 14 17 18 24 26
After 4th pass: 10 13 14 17 18 24 26
After 5th pass: 10 13 14 17 18 24 26
What is the number of comparisons and swaps in each pass? Specify your answer in each pass.
c) What is the maximum number of comparisons and the maximum number of swaps that might be needed in b) if the sequence is in descending order. (2 Marks)
d) Compare the below sorting algorithms worst performance in terms of Big-O ( All correct, 1 Mark)
QuickSort
Selection Sort
Insertion Sort
Q3. (5 Marks)
a) Write down the number sequence with the following order traversal by referencing the following tree.
(1) preorder
(2) inorder
(3) postorder (0.5 each, 1.5 Marks)
b) Construct a Binary Search Tree (BST) by inserting the following keys (from left to right): The tree initially is empty. key ={17, 9, 26, 12, 11, 7, 30, 20, 21, 10} (2.5 Marks)
c) By using the BST from question Q3b, draw the BST after the key 17 is deleted (1 Marks)
iii)

algorithm and data structure

PE424001 Algorithm and Data Structure
Assignment 1
(25% of the module score)
Q1. (10 Marks) With an infix expression in the form of :
((A-B)+C*(D+E))-(F+G)
a) What is the prefix expression? Illustrates your steps using a Stack data structure. (4 Marks)
b) Verify your result by assigning the values to variables and shows your steps. (4 Marks)
A=7 , B=6, C=5, D=4, E=3, F=2, G=1
c) What is the final answer in b)? (1 Mark)
d) Give one example in which Stack is always used. (1 Mark)
Q2. (10 Marks) Given an input array
[ 5 2 6 1 7 9 4 3]
a) Trace the action of:
1 Selection Sort (1 Mark)
2 Insertion Sort (1 Mark)
b) Refer to the following number list which is sorted by bubble sort and in ascending order. (5 Marks)
Initial list: 18, 17, 13, 26, 10, 14, 24
After 1st pass: 17 13 18 10 14 24 26
After 2nd pass: 13 17 10 14 18 24 26
After 3rd pass: 13 10 14 17 18 24 26
After 4th pass: 10 13 14 17 18 24 26
After 5th pass: 10 13 14 17 18 24 26
What is the number of comparisons and swaps in each pass? Specify your answer in each pass.
c) What is the maximum number of comparisons and the maximum number of swaps that might be needed in b) if the sequence is in descending order. (2 Marks)
d) Compare the below sorting algorithms worst performance in terms of Big-O ( All correct, 1 Mark)
QuickSort
Selection Sort
Insertion Sort
Q3. (5 Marks)
a) Write down the number sequence with the following order traversal by referencing the following tree.
(1) preorder
(2) inorder
(3) postorder (0.5 each, 1.5 Marks)
b) Construct a Binary Search Tree (BST) by inserting the following keys (from left to right): The tree initially is empty. key ={17, 9, 26, 12, 11, 7, 30, 20, 21, 10} (2.5 Marks)
c) By using the BST from question Q3b, draw the BST after the key 17 is deleted (1 Marks)
iii)